package com.LeeCode;

import java.util.ArrayList;
import java.util.Arrays;
import java.util.List;

/**
 * 节点序列的最大得分
 */

public class Code2242 {
    public static void main(String[] args) {

    }


    public int maximumScore(int[] scores, int[][] edges) {
        int n = scores.length;
        List<int[]>[] graph = new List[n];
        Arrays.setAll(graph, i -> new ArrayList<>());
        for (int[] edge : edges) {
            int x = edge[0], y = edge[1];
            graph[x].add(new int[]{scores[y], y});
            graph[y].add(new int[]{scores[x], x});
        }

        // 优化只需要保留前三个，对于x，极端情况下y和b都是x的邻居，需要第三个点来当a
        for (int i = 0; i < n; i++)
            if (graph[i].size() > 3) {
                graph[i].sort((a, b) -> (b[0] - a[0]));
                graph[i] = new ArrayList<>(graph[i].subList(0, 3));
            }

        int ans = -1;
        for (int[] e : edges) {
            int x = e[0], y = e[1];
            for (int[] p : graph[x]) {
                int a = p[1];
                for (int[] q : graph[y]) {
                    int b = q[1];
                    if (a != y && b != x && a != b)
                        ans = Math.max(ans, p[0] + scores[x] + scores[y] + q[0]);
                }
            }
        }
        return ans;
    }
}
